﻿#ifndef LK_BLOCKMEMORYALLOC_
#define LK_BLOCKMEMORYALLOC_
namespace LK
{
	/**
	@brief 包含BlockMemory内存池中的内存块的操作方法.
	@note 为了加速分配过程，节点将使用size_t []动态数组的形式，BlockMemoryNode类提供操作size_t []数组节点的方法
	@note size_t p[]数组中内容安排：
	@note p[0]：该位置记录已使用元素数
	@note p[1]：该位置记录可用元素对应的位置数组索引（>=2）
	@note p[2~iSize+1]：内容可用信息记录图表，内容元素数为iSize
	@note p[iSize+2~BufferLength-1]：内容纪录部分，内容元素数为bSize*/
	struct BlockMemoryNode
	{
		/**
		@brief 将位置记录部分的index位置设置为其相反的状态
		@param [传入,写出]参数p表示内存块
		@param [传入]参数index表示索引号*/
		static void set(size_t*p, size_t index)
		{
			p[index / (sizeof(size_t) * 8) + 2] ^= ((size_t)(1ull << (sizeof(size_t) * 8 - 1))) >> (index&(sizeof(size_t) * 8 - 1));
		}
		/**
		@brief 获取一个可用的位置的指针并将该位置设置为不可用
		@param [传入,写出]参数p表示内存块
		@param [传入]参数iLen表示信息记录部分元素数，包括p[0]和p[1]
		@param [传入]参数size表示每个分配单元的大小，这里按字节对齐
		@return 如果申请成功，则返回申请到的内存指针，否则返回NULL*/
		static void*get(size_t*p, size_t iLen, size_t size)
		{
			size_t t = p[1];
			size_t i = t;
			while (p[i] == 0)//i从2开始
			{
				if (++i == iLen)i = 2;//iLen恰好为终止位置索引
				if (i == t)return (void*)NULL;
			}
			p[1] = i;
			size_t tmp = (i - 2)*(sizeof(size_t) * 8) + Bits::LeftZeroCount(p[i]);
			set(p, tmp);
			++p[0];
			return (unsigned char*)(p + iLen) + tmp*size;
		}
		/**
		@brief 释放内存
		@param [模板]参数size表示分配单元大小
		@param [传入]参数pf为需要释放的内存
		@param [传入,写出]参数p表示内存块
		@param [传入]iLen表示内存块信息记录部分元素数
		@param [传入]参数bLen表示内容区域元素数
		@return 如果pf所指内存不在该内存块则返回false，如果成功释放返回true，当指针失效（多次释放相同指针）时将抛出异常
		@exception XPointerFailureException*/
		template<size_t size>static bool free(void* pf, size_t*p, size_t iLen, size_t bLen)
		{
			size_t index = ((unsigned char*)pf - (unsigned char*)(p +iLen)) / size;
			if (index>=bLen)
				return false;
			if (((p + 2)[index / (sizeof(size_t) * 8)]
				& (((size_t)(1ull << (sizeof(size_t) * 8 - 1))) >> (index&(sizeof(size_t) * 8 - 1)))) != 0)
			{
				Throw<PPointerFailureException>();//指针失效，抛出异常
			}
			size_t tmp = index;
			set(p, tmp);
			--p[0];
			p[1] = tmp / (sizeof(size_t) * 8)+2;
			return true;
		}
		/**
		@brief 分配一块内存
		@param [传入,写出]参数p表示内存块
		@param [传入]参数iLen表示信息记录部分元素数
		@param [传入]参数size表示分配单元大小
		@return 如果分配成功，返回分配得到的内存指针，失败返回NULL*/
		inline static void* alloc(size_t*p, size_t iLen, size_t size)
		{
			return get(p, iLen, size);
		}
		/**
		@brief初始化
		@param [传入,写出]参数p表示内存块
		@param [传入]参数iLen表示信息记录部分元素数
		@param [传入]参数bLen表示内容区域元素数*/
		static void Initial(size_t*p, size_t iLen, size_t bLen)
		{
			p[0] = 0; p[1] = 2;
			for (size_t i = 2; i < iLen ; ++i)p[i] = (size_t)-1;
			size_t mov = ((iLen-2)* sizeof(size_t) * 8 - bLen);
			p[iLen -1] <<= mov;
		}
		/**
		@brief 根据内容区域元素数来计算信息记录区元素数量
		@param [传入]参数bLen表示内容区域元素数
		@return 返回信息记录区域元素数*/
		static size_t GetIndexLen(size_t bLen)
		{
			return 2+(bLen + sizeof(size_t) * 8 - 1) / (sizeof(size_t) * 8);
		}
		/**
		@brief 根据内存块总元素数和分配单元大小计算内容区域元素数
		@param [传入]参数bufferLength表示内存块总元素数
		@param [传入]参数size 表示分配单元大小
		@return 返回内容区域元素数*/
		static size_t GetBlockLen(size_t bufferLength, size_t size)
		{
			size_t result = ((bufferLength - 2)*sizeof(size_t) * 8) / (size * 8 + 2);
			while (((result + 1)*sizeof(size_t) * 8 - 1) / (sizeof(size_t) * 8) + (size*result + sizeof(size_t) - 1) / (sizeof(size_t) * 8) > bufferLength - 2)--result;
			return result;
		}
	};
	/**
	@brief 表示块内存池对象，用以进行分配单元大小为size字节的内存的分配
	@param [模板]参数size表示分配单元大小
	@note BlockMemory分配的内存大小是固定的*/
	template<size_t size>class BlockMemory
	{
		/**
		@brief 内存块数组，检索以分配内存（按地址升序排列）*/
		size_t** pArr;
		/**
		@brief 内存块数组元素数*/
		size_t arrSize;
		/**
		@brief 互斥对象，用以进行线程同步*/
		SpinMutex mtStatic;
		/**
		@brief 节点总数*/
		size_t NodeCount;
		/**
		@brief 已使用节点总数*/
		size_t UsedCount;
		/**
		@brief 上次有内容的节点索引*/
		size_t TmpIndex;
		/**
		@brief 信息记录部分元素数*/
		size_t IndexLength;
		/**
		@brief 内容部分元素数*/
		size_t BlockLength;
		/**
		@brief 内存块总元素数*/
		size_t BufferLength;
		/**
		@brief 新增节点
		@param 参数p指向已经由BlockMemoryNode::Initial进行初始化的内存*/
		void AddNode(size_t*p);
		/**禁止复制和赋值*/
		BlockMemory(BlockMemory const&){}
		BlockMemory&operator=(BlockMemory const&){}
	public:
		/**
		@brief 构造函数
		@param [传入]参数enableMutex用以指定是否进行多线程同步
		@param [传入]参数bufferLength用以指定块总元素数（以size_t的大小为单位）
		@note 注意：块大小在对象生成后需要释放所有内存才能修改*/
		BlockMemory(bool enableMutex = true, size_t bufferLength = 65536 / sizeof(size_t)-8);
		/**
		@brief 析构函数*/
		~BlockMemory(){ RemoveAll(); }
		/**
		@brief 是否启用多线程同步（默认使用）
		@note 作为公开的成员，这里可以通过直接为EnableMutex赋值来决定是否启用同步*/
		volatile bool EnableMutex;
		/**
		@brief 分配一块size字节大小的内存，并返回其指针*/
		void* Alloc();
		/**
		@brief 释放Alloc所分配的内存
		@param [传入]参数p指向需要释放的内存
		@return 当p为NULL或者成功释放时返回true，当p不在内存块中时返回false，当释放失败时将抛出异常
		@exception XPointerFailureException*/
		bool Free(void*p);
		/**
		@brief 移除未使用的内存块*/
		void RemoveEmpty();
		/**
		@brief 移除所有内存块（如果有内存未释放将抛出异常）
		@exception PException*/
		void RemoveAll();
		/**
		@brief 修改块元素数，（以size_t为元素的数组元素数）
		@param [传入]参数bufferLength表示块元素数
		@note 改变块元素数需要释放所有内存
		@exception PException*/
		void ChangeBufferSize(size_t bufferLength);
		/**
		@brief 获取当前块元素数
		@return 返回当前每个内存块的元素数*/
		size_t GetBufferSize(){ return BufferLength; }
		/**
		@brief 默认的共享内存池*/
		static BlockMemory&DefaultPool(){ static BlockMemory bm; return bm; }
	};
	template<size_t size>void BlockMemory<size>::AddNode(size_t*p)
	{
		if (pArr == NULL)
		{
			pArr =Memory::Malloc<size_t*>(4);
			arrSize = 4;
			*pArr = p;
			TmpIndex = 0;
		}
		else
		{
			if (NodeCount == arrSize)
			{
				++arrSize;
				void* pp = Memory::Realloc(pArr, arrSize);
                                if (pp == 0)Throw<POutOfMemoryException>();//申请内存失败
				pArr = (size_t**)pp;
			}
			if (p > pArr[NodeCount-1])
			{
				pArr[TmpIndex = NodeCount] = p;
			}
			else if (p < pArr[0])
			{
				for (size_t i = NodeCount; i > 0; --i)
				{
					pArr[i] = pArr[i - 1];
				}
				pArr[0] = p;
				TmpIndex = 0;
			}
			else
			{
				size_t high = NodeCount - 1;
				size_t low = 1;
				size_t current = NodeCount / 2;
				for (;;)
				{
					if (pArr[current]>p)
					{
						high = current;
						if (pArr[current - 1] < p)break;
						size_t tmp = (low + current) / 2;
						if (current == tmp)
						{
							--current;
						}
						else current = tmp;
					}
					else if (pArr[current] < p)
					{
						low = current;
						size_t tmp = (current + high) / 2;
						if (current == tmp)
						{
							++current;
						}
						else current = tmp;
					}
					else break;
				}
				for (size_t i = NodeCount; i>current; --i)
				{
					pArr[i] = pArr[i - 1];
				}
				pArr[current] = p;
				TmpIndex = current;
			}
		}
		++NodeCount;
	}
	template<size_t size>BlockMemory<size>::BlockMemory(bool enableMutex, size_t bufferLength)
    {
        BufferLength=bufferLength;
        pArr=NULL;
        UsedCount=0;
        TmpIndex=0;
        arrSize=0;
        NodeCount=0;
        EnableMutex=enableMutex;
		BlockLength = BlockMemoryNode::GetBlockLen(bufferLength, size);
		IndexLength = BlockMemoryNode::GetIndexLen(BlockLength);
	}
	template<size_t size>void* BlockMemory<size>::Alloc()
	{
		void*p;
		bool en = EnableMutex;
		if (en)mtStatic.Lock();
		if (UsedCount == NodeCount)
		{
			size_t* t = Memory::Malloc<size_t>(BufferLength);
			BlockMemoryNode::Initial(t, IndexLength, BlockLength);
			p = BlockMemoryNode::alloc(t, IndexLength, size);
			AddNode(t);
		}
		else
		{
			size_t t = TmpIndex;
			if (pArr[t][0] == BlockLength)
			{
				for (;;)
				{
					if (++t == NodeCount)t = 0;
					if (pArr[t][0] != BlockLength)break;
				}
				TmpIndex = t;
			}
			p = BlockMemoryNode::alloc(pArr[t], IndexLength, size);
			if (pArr[t][0] == BlockLength)
				UsedCount++;
		}
		if (en)mtStatic.UnLock();
		return p;
	}
	template<size_t size>bool BlockMemory<size>::Free(void*p)
	{
		if (!p)return true;
		bool en = EnableMutex;
		if (en)mtStatic.Lock();
		if (pArr)
		{
			if (NodeCount == 1 || pArr[1] > p)
			{
				TmpIndex = 0;
				if (BlockMemoryNode::free<size>(p, pArr[0], IndexLength, BlockLength))
				{
					if(pArr[0][0] == BlockLength - 1)UsedCount--;
					goto True;
				}
			}
			else if (pArr[NodeCount - 1] < p)
			{
				TmpIndex = NodeCount - 1;
				if (BlockMemoryNode::free<size>(p, pArr[NodeCount - 1], IndexLength, BlockLength))
				{
					if (pArr[NodeCount - 1][0] == BlockLength - 1)UsedCount--;
					goto True;
				}
			}
			else//二分法查找
			{
				size_t high = NodeCount - 1;
				size_t low = 0;
				size_t current = high / 2;
				for (;;)
				{
					if (pArr[current]>p)
					{
						high = current;
						size_t tmp = (low + current) / 2;
						if (current == tmp)
							--current;
						else current = tmp;
					}
					else if (pArr[current + 1] < p)
					{
						low = current;
						size_t tmp = (current + high) / 2;
						if (current == tmp)
						{
							if (pArr[current + 1]>p)break;
							++current;
						}
						else current = tmp;
					}
					else break;
				}
				if (BlockMemoryNode::free<size>(p, pArr[current], IndexLength, BlockLength))
				{
					TmpIndex = current;
					if(pArr[current][0] == BlockLength - 1)UsedCount--;
					goto True;
				}
			}
		}
		if (en)mtStatic.UnLock();
		return false;
	True:;
		if (en)mtStatic.UnLock();
		return true;
	}
	template<size_t size>void BlockMemory<size>::RemoveEmpty()
	{
		bool en = EnableMutex;
		if (en)mtStatic.Lock();
		for (size_t t = 0, lt = 0; lt < NodeCount; ++lt)
		{
			pArr[t] = pArr[lt];
			if (pArr[t][0] == 0)
			{
				Memory::Free(pArr[t]);
				if (TmpIndex == t)TmpIndex = 0;
				else if (TmpIndex>t)--TmpIndex;
				--NodeCount;
			}
			else ++t;
		}
		if (en)mtStatic.UnLock();
	}
	template<size_t size>void BlockMemory<size>::RemoveAll()
	{
		bool en = EnableMutex;
		if (en)mtStatic.Lock();
		if (UsedCount != 0)
		{
			if (en)mtStatic.UnLock();
			Throw<PException>(L"有内容未释放");//有部分内容未释放
		}
		for (size_t t = 0; t < NodeCount; ++t)
		{
			Memory::Free(pArr[t]);
		}
		Memory::Free(pArr);
		pArr = NULL;
		NodeCount = 0;
		arrSize = 0;
		if (en)mtStatic.UnLock();
	}
	template<size_t size>void BlockMemory<size>::ChangeBufferSize(size_t bufferLength)
	{
		RemoveAll();
		BlockLength = BlockMemoryNode::GetBlockLen(bufferLength, size);
		IndexLength = BlockMemoryNode::GetIndexLen(BlockLength);
	}
}
#endif
